In distributed architectures, processors may communicate packets to one another through a switch. Some architectures use an N-by-(N-1) switch, which has a separate path from each processor to every other processor. Thus, congestion of one path does not affect other paths. N-by-(N-1) switches, however, are typically expensive. Moreover, processors may be added to a switch over time, creating the need for more paths at the switch.
Other architectures use a non-N-by-(N-1) switch, where processors share paths of the switch. Non-N-by-(N-1) switches, however, may experience head-of-line blocking problems. In this situation, if a processor is congested and cannot accept any more packets, packets for the processor remain in a queue that is shared by other processors. Until the waiting packets are taken from the queue by the processor, packets that arrive after the waiting packets cannot be taken by the other processors. This causes a packet buildup in the shared queue. Accordingly, congestion at the one processor may deteriorate service for other processors that share the same queue.